#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/5/9 17:40
# ===========================================
#       题目名称： 40. 组合总和 II
#       题目地址： https://leetcode.cn/problems/combination-sum-ii/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================

import copy as _cp

class Solution:
    """
        给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
    candidates 中的每个数字在每个组合中只能使用 一次 。
    注意：解集不能包含重复的组合。
    """

    def combinationSum2(self, candidates, target):
        # 返回值
        result = []
        # 清除大于target的
        cur_index = 0
        while cur_index < len(candidates):
            if candidates[cur_index] > target:
                del candidates[cur_index]
                continue
            elif candidates[cur_index] == target:
                result.append([candidates[cur_index]])
            cur_index += 1
        # 排序一下
        candidates.sort()
        # 返回字典 k () {tuple} 当前已使用的  v [] 当前未使用的数据
        result_dict = {}
        # 首次遍历
        for i in range(len(candidates)):
            temp_candidates = _cp.deepcopy(candidates)
            del temp_candidates[i]
            result_dict[(candidates[i],)] = temp_candidates
        while result_dict:
            possibility_result_dict = {}    # 有可能的返回字典
            for k, v in result_dict.items():
                cur_k_val = sum(k)
                for i in range(len(v)):
                    item = v[i]
                    if item + cur_k_val == target:
                        cp_k = list(_cp.deepcopy(k))
                        cp_k.append(item)
                        cp_k.sort()
                        result.append(cp_k)
                    if item + cur_k_val > target:
                        break
                    if item + cur_k_val < target:
                        cp_k = list(_cp.deepcopy(k))
                        cp_k.append(item)
                        cp_k.sort()
                        # 排除item
                        cp_v = _cp.deepcopy(v)
                        del cp_v[i]
                        possibility_result_dict[tuple(cp_k)] = cp_v
            result_dict = possibility_result_dict
        # 去重
        result = set(tuple(item) for item in result)
        # 恢复
        result = list(list(item) for item in result)
        return result



if __name__ == "__main__":
    s = Solution()
    print(s.combinationSum2(candidates=[10, 1, 2, 7, 6, 1, 5], target=8))  # [[1, 1, 6],[1, 2, 5],[1, 7],[2, 6]]
    print(s.combinationSum2(candidates=[2, 5, 2, 1, 2], target=5))  # [[1,2,2],[5]]
